package com.itheima.mysort;

public class A05_QuickDemo2 {
    public static void main(String[] args) {
        //快速排序2

        //等待排序的数据
        int[] arr = {7, 4, 2, 13, 1, 3, 12, 10, 5, 8, 9, 6, 11};

        //用来排序的方法
        quickSort(arr,0,arr.length-1);

        //输出查看
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    public static void quickSort(int[] arr, int i, int j) {

        //先把start和end存起来，后面要用
        int start=i;
        int end=j;

        //递归出口
        if(start > end) {
            return;
        }


        //定义一个基准数
        int baseNumber=arr[i];

        //开始移动start和end寻找
        while (end!=start) {
            //先找end
            while (true){
                //找到了直接跳出
                if(arr[end]<baseNumber||end<=start){
                    break;
                }
                //没找到换下一个位置继续找
                end--;
            }
            //再找start
            while (true){
                //找到了直接跳出
                if(arr[start]>baseNumber||end<=start){
                    break;
                }
                //没找到换下一个位置继续找
                start++;
            }
            //代码到这里就说明找到了，直接交换就好
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;

            //找到end和start重合，说明全部找完了，整个循环结束
        }
        //代码运行到这里说明第一个基准数找到了自己的位置，基准数归位
        int temp=arr[start];
        arr[start]=arr[i];
        arr[i]=temp;

        //递归不断找下一部分基准数该在的位置
        //左边
        quickSort(arr,i,start-1);
        //右边
        quickSort(arr,start+1,j);


    }
}
